"""
Reverse bits of a given 32 bits unsigned integer.

For example, given input 43261596 (represented in binary as 00000010100101000001111010011100), return 964176192 (represented in binary as 00111001011110000010100101000000).

Follow up:
If this function is called many times, how would you optimize it?

Related problem: Reverse Integer
"""

class Solution:
    # @param n, an integer
    # @return an integer
    def __init__(self):
        self.tab = [0x0, 0x8, 0x4, 0xc, 0x2, 0xa, 0x6, 0xe, 0x1, 0x9, 0x5, 0xd, 0x3, 0xb, 0x7, 0xf]
        self.mask = [0x0000000F, 0x000000F0, 0x00000F00, 0x0000F000, 0x000F0000, 0x00F00000, 0x0F000000, 0xF0000000]
        self.multi = [0, 4, 8, 12, 16, 20, 24, 28]
    def reverseBits(self, n):
        ans = 0
        for i in range(0, 8):
            a = (n&self.mask[i])>>self.multi[i]
            b = self.tab[a]
            ans += b << (28-self.multi[i])
        return ans

if __name__ == '__main__':
    print Solution().reverseBits(43261596)

